package com.everyday.practice.leetCode;

public class Title74 {
    public static void main(String[] args) {
        Title74 title74=new Title74();
        int[][] matrix=new int[3][4];
        matrix[0][0]=1;
        matrix[0][1]=3;
        matrix[0][2]=5;
        matrix[0][3]=7;
        matrix[1][0]=10;
        matrix[1][1]=11;
        matrix[1][2]=16;
        matrix[1][3]=20;
        matrix[2][0]=23;
        matrix[2][1]=30;
        matrix[2][2]=34;
        matrix[2][3]=60;
        System.out.println(title74.searchMatrix(matrix,6));;
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i=0;i<matrix.length;i++){
            if (target>matrix[i][matrix[i].length-1]){
                continue;
            }else{
                return search(matrix[i],target);
            }
        }
        return false;
    }

    public boolean search(int[] nums, int target){
        if (nums.length<=2){
            if (nums[0]==target||nums[nums.length-1]==target){
                return true;
            }else {
                return false;
            }
        } else{
            int index=(int) Math.ceil(Double.valueOf(nums.length) / 2);
            if (nums[index]==target){
                return true;
            }else if (nums[index]>target){
                int[] left=new int[index];
                for (int i=0;i<index;i++){
                    left[i]=nums[i];
                }
                return search(left,target);
            }else{
                int[] right=new int[nums.length-index];
                for (int i=0;i<nums.length-index;i++){
                    right[right.length-i-1]=nums[nums.length-i-1];
                }
                return search(right,target);
            }
        }
    }
}
